package com.cqs.leetcode.ds.union.find;



import com.google.common.collect.Lists;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

/**
 * lixw
 * 2021/11/1
 **/
public class NumberIslands200 {


    public int numIslands(char[][] grid) {
        //BFS
        Queue<int[]> q = new ArrayDeque<>();
        boolean[][] visited = new boolean[grid.length][grid[0].length];
        //种子
        int cnt = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (visited[i][j]) continue;
                visited[i][j] = true;
                if (grid[i][j] == '1') {
                    q.add(new int[]{i, j});
                    ++cnt;
                }
                //遍历
                while (q.size() > 0) {
                    int[] poll = q.poll();
                    //北 东 南 西 [顺时针]
                    handlePoint(grid,visited,q,poll,'N');
                    handlePoint(grid,visited,q,poll,'E');
                    handlePoint(grid,visited,q,poll,'S');
                    handlePoint(grid,visited,q,poll,'W');
                }
            }
        }
        return cnt;
    }

    private void handlePoint(char[][] grid,  boolean[][] visited,Queue<int[]> q, int[] poll,char  dir) {
        int x = 0 ,y = 0;
        //北 东 南 西
        switch (dir) {
            case 'N':
                if (poll[0] <= 0) {
                    return;
                }
                x = poll[0] - 1;
                y = poll[1];
                break;
            case 'E':
                if (poll[1] + 1 >= grid[0].length) {
                    return;
                }
                x = poll[0] ;
                y = poll[1] + 1;
                break;
            case 'S':
                if (poll[0] + 1 >= grid.length) {
                    return;
                }
                x = poll[0] + 1;
                y = poll[1];
                break;
            case 'W':
                if (poll[1] <= 0) {
                    return;
                }
                x = poll[0] ;
                y = poll[1] - 1;
                break;
            default:
        }

        if (!visited[x][y]) {
            if (grid[x][y] == '1') {
                q.add(new int[]{x , y});
            }
        }
        visited[x][y] = true;
    }

    public static void main(String[] args) {

        List<char[][]> cases = new ArrayList<>();
        cases.add(new char[][]{{'1','1','0','0','0'},
                {'1','1','0','0','0'},
                {'0','0','1','0','0'},
                {'0','0','0','1','1'}});

        NumberIslands200 ni = new NumberIslands200();
        for (char[][] grids : cases) {
            int num = ni.numIslands(grids);
            System.out.println(Lists.newArrayList(grids)+"---> " + num);
        }


    }


}
